/*************************************************************************
 * File Name:    Reverse_Nodes_in_k-Group.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/13 23:39:27
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Reverse Nodes in k-Group
 |
 | Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
 |
 | If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
 |
 | You may not alter the values in the nodes, only nodes itself may be changed.
 |
 | Only constant memory is allowed.
 |
 | For example,
 | Given this linked list: 1->2->3->4->5
 | For k = 2, you should return: 2->1->4->3->5
 | For k = 3, you should return: 3->2->1->4->5
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	ListNode *reverseKGroup(ListNode *head, int k)
	{
		if (k == 0 || k == 1) return head;
		
		ListNode *beg, *end;
        ListNode *it = head;
        for (int i = 1; i <= k; ++i) {
		    if (it == NULL) return head;
		    
    	    if (i == 1) beg = it;
    	    else if (i == k) end = it;
    	    
	        it = it->next;
        }
        reverseOneGroup(beg, end);

        ListNode *ans = end;
        ListNode *tail = beg;
        int cnt = 0;

        beg = end = NULL;
        while (it != NULL) {
		    ++cnt;
    	    if (cnt == 1) {
    	        beg = it;
    	        it = it->next;
    	    } else if (cnt == k) {
	    		end = it;
	    		it = it->next;
		        reverseOneGroup(beg, end);
    		    tail->next = end;
    	    	tail = beg;
	    	    cnt = 0;
	    	    
	    	    beg = end = NULL;
            } else {
                it = it->next;
            }
        }
        tail->next = beg;
        return ans;
    }
private:
	// [head, tail]
	void reverseOneGroup(ListNode *head, ListNode *tail)
	{
		ListNode *thead = head;
		ListNode *t, *it;

		it = head->next;
		while (true) {
			t = it->next;
			it->next = thead;
			thead = it;
			if (it == tail) return;
			it = t;
		}
    }
};

int
main(int argc, char *argv[])
{
    ListNode *head = new ListNode(1);

    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = NULL;

    Solution sol;
    ListNode *t = sol.reverseKGroup(head, 3);

    while (t != NULL) {
        cout << t->val << " ";
        t = t->next;
    }
    cout << endl;

    return 0;
}
